package com.gxc.string;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目6
 * Z 字形变换
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

 P   A   H   N
 A P L S I I G
 Y   I   R
 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 *
 */
public class Zconvert {

    public static void main(String[] args) {
        String s = "PAYPALISHIRING";
        int numRows = 4;
        System.out.println(handle(s, numRows));
        System.out.println(handle2(s, numRows));

        System.out.println(handle(s, numRows).equals(handle2(s, numRows)));
    }

    //通过下标位置计算
    public static String handle(String s, int numRows) {
        if (numRows == 1 || numRows >= s.length()) {
            return s;
        }
        char[] chars = s.toCharArray();
        int length = 2 * numRows - 2;
        int size = length;

        StringBuffer buffer = new StringBuffer();
        int pos = 0;
        int i = 0;
        while (i<numRows) {
            boolean flag = true;
            while (pos<s.length()) {
                buffer.append(chars[pos]);
                if (i>0 && i<numRows-1) {
                    if (flag) {
                        size = length-2*i;
                    } else {
                        size = length-size;
                    }
                    flag=!flag;
                }
                pos +=  size;
            }
            i++;
            pos = i;
            size = length-2*i;
            if (size == 0) size = 2 * numRows - 2;
        }
        return buffer.toString();
    }

    /**
     * 构建二位空间数组
     * @param s
     * @param numRows
     * @return
     */
    private static String handle2(String s, int numRows) {
        if (numRows ==1 || numRows>=s.length()) return s;
        char[] charArray = s.toCharArray();

        StringBuffer buffer = new StringBuffer();
        char[][] chars = new char[numRows][s.length()];

        int row = 0;
        int col = 0;
        boolean direction = true;
        for (int i = 0; i < charArray.length; i++) {
            if (row == numRows-1) {
                direction = false;
            } else if (row == 0) {
                direction = true;
            }
            chars[row][col] = charArray[i];
            if (direction) {
                row++;
            } else {
                row--;
                col++;
            }
        }
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars[i].length; j++) {
                if (chars[i][j] != 0) {
                    buffer.append(chars[i][j]);
                }
            }
        }
        return buffer.toString();
    }

    //官方解1
    public String process(String s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r * 2 - 2;
        //当我们在矩阵上填写字符时，会向下填写 r 个字符，然后向右上继续填写 r−2 个字符，最后回到第一行，
        // 因此 Z 字形变换的周期 t=r+r−2=2r−2，每个周期会占用矩阵上的 1+r−2=r−1 列。

        int c = (n + t - 1) / t * (r - 1);
        char[][] mat = new char[r][c];
        for (int i = 0, x = 0, y = 0; i < n; ++i) {
            mat[x][y] = s.charAt(i);
            if (i % t < r - 1) {
                ++x; // 向下移动
            } else {
                --x;
                ++y; // 向右上移动
            }
        }
        StringBuffer ans = new StringBuffer();
        for (char[] row : mat) {
            for (char ch : row) {
                if (ch != 0) {
                    ans.append(ch);
                }
            }
        }
        return ans.toString();
    }

    //压缩矩阵空间

    /**
     * 压缩矩阵空间
     * 注意到每次往矩阵的某一行添加字符时，都会添加到该行上一个字符的右侧，
     * 且最后组成答案时只会用到每行的非空字符。
     * 因此我们可以将矩阵的每行初始化为一个空列表，每次向某一行添加字符时，添加到该行的列表末尾即可。
     * @param s
     * @param numRows
     * @return
     */
    public String process2(String s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        StringBuffer[] mat = new StringBuffer[r];
        for (int i = 0; i < r; ++i) {
            mat[i] = new StringBuffer();
        }
        for (int i = 0, x = 0, t = r * 2 - 2; i < n; ++i) {
            mat[x].append(s.charAt(i));
            if (i % t < r - 1) {
                ++x;
            } else {
                --x;
            }
        }
        StringBuffer ans = new StringBuffer();
        for (StringBuffer row : mat) {
            ans.append(row);
        }
        return ans.toString();
    }

    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }


}
